import java.util.HashMap;
import java.util.Vector;


public class GLC {
	
	String[] alfabeto;
	String inicial;
	String[] variaveis;
	HashMap<String, Vector<String>> regras;
	
	private String variavel;
	private int inicio;
	
	public GLC() {
		this.regras = new HashMap<String, Vector<String>>();
	}
	
	public boolean testarCadeia(String cadeia){
		
		boolean retorno = false;
		
		Vector<String> geradores = new Vector<String>();
		geradores.add(inicial);
		
		while(geradores.size() > 0){
			
			String str = geradores.remove(0);
			
			if(contemVariavel(str)){
				String sub1 = str.substring(0, inicio);
				String sub2 = str.substring(inicio+variavel.length());
				
				for(String s : regras.get(variavel)){
					if(s.equals("e")){
						if((sub1 + sub2).length() > 0){
							s = "";
						}
					}
					
					if(tamanho(sub1+s+sub2) <= cadeia.length()){
						geradores.add(sub1+s+sub2);
					}
				}
			} else {
				retorno = str.equals(cadeia);
				if(retorno) geradores.clear();
			}
		}
		
		return retorno;
	}

	private int tamanho(String string) {
		int length = string.length();
		
		for(String s : variaveis){
			if(string.contains(s)) length-=s.length();
		}
		
		return length;
	}

	private boolean contemVariavel(String cadeia) {
		boolean retorno = false;
		
		for(String var : variaveis){
			retorno = retorno|cadeia.contains(var);
			if(cadeia.contains(var)){
				retorno = true;
				inicio = cadeia.indexOf(var);
				variavel = var;
			}
		}
		
		return retorno;
	}
}
